# -*- coding: UTF-8 -*-
from typing import List
from leetcode_helper import TestcaseHelper, SolutionBase


class Solution(SolutionBase):
    def __init__(self):
        self.max_total = 0

    def back_track(self, statements, player, good, bad):
        # base case
        if player == len(statements):
            self.max_total = max(len(good), self.max_total)
            return

            # backtracking
        for i in range(player, len(statements)):
            # prune
            if i in bad:
                continue

            new_good = [j for j in range(len(statements[i])) if statements[i][j] == 1]
            new_good.append(i)
            new_bad = [j for j in range(len(statements[i])) if statements[i][j] == 0]

            new_good = [x for x in new_good if x not in good]
            new_bad = [x for x in new_bad if x not in bad]

            if len(set(good + new_good).intersection(set(bad + new_bad))) > 0:
                # prune
                pass
            else:
                self.back_track(statements, i + 1, good + new_good, bad + new_bad)
            if i not in bad:
                bad.append(i)

        if len(set(good).intersection(set(bad))) > 0:
            pass
        else:
            self.max_total = max(len(good), self.max_total)

        return
            
    # 解题的方法，命名和Leetcode的保持一致即可
    def maximumGood(self, statements: List[List[int]]) -> int:
        self.back_track(statements, 0, [],[])
        return self.max_total


if __name__ == '__main__':
    # 按照leetcode的题目说明，将基本的test case填入
    # 每条case的最后一个元素是正确的结果，即期待的结果
    # 使用元组来保存输入的数据，期待的结果
    testcases = [
        ([[2, 0], [0, 2]], 1),
        ([[2, 1, 2], [1, 2, 2], [2, 0, 2]], 2),
    ]

    for case_item in testcases:
        # 获取测试用的case和期待的执行结果
        solution = Solution()
        input1 = case_item[0]
        expect = case_item[len(case_item) - 1]
        exec_result = solution.maximumGood(input1)

        # 判断执行结果，输出提示信息
        check_result = solution.check_result(expect, exec_result)
        TestcaseHelper.print_case(check_result, case_item, exec_result)

